import random


class Sort:
    def __init__(self, n):  # n是要排序的数量
        self.length = n  # 快排中列表的长度
        self.arr = [0] * n  # 初始化
        self.random_data()
        # self.arr = [1,2,3,4,5,6,7,8,9,18]
        self.count = 0  # 记录递归次数

    def random_data(self):
        for i in range(self.length):
            self.arr[i] = random.randint(0, 99)  # 左闭右闭

    # 快速排序
    def QuickSort(self, low, high):
        arr = self.arr
        if low < high:
            mid = self.Partition(low, high)
            self.QuickSort(low, mid - 1)
            self.QuickSort(mid + 1, high)
        self.count += 1

    def Partition(self, low, high):
        arr = self.arr
        mid = arr[low]
        while low < high:
            while low < high and arr[high] > mid:
                high -= 1
            arr[low] = arr[high]
            while low < high and arr[low] < mid:
                low += 1
            arr[high] = arr[low]
        arr[low] = mid
        return low

    def adjust_max_heap(self, pos, arr_len):  # 调整某一棵子树为大根堆
        '''
        pos是被调整节点的下标，arr_len是列表长度
        :param pos:
        :param arr_len:
        :return:
        '''
        arr = self.arr
        dad = pos
        son = 2 * dad + 1
        while son < arr_len:  # 左孩子小于列表长度  即遍历到最后一个有孩子的父节点即可
            if son + 1 < arr_len and arr[son] < arr[son + 1]:  # 若有右孩子且右孩子更大
                son += 1  # 找到更大的那个孩子的下标
            if arr[son] > arr[dad]:
                arr[dad], arr[son] = arr[son], arr[dad]  # 交换
                dad = son  # 向被调整的孩子子树遍历
                son = 2 * dad + 1
            else:
                break

    def Heap_Sort(self):
        # 把列表调整为大根堆（建堆）     #最后一个有孩子父节点  到0  步长为-1（倒着来）
        for parent in range(self.length // 2 - 1, -1, -1):
            self.adjust_max_heap(parent, self.length)

        arr = self.arr
        arr[0], arr[self.length - 1] = arr[self.length - 1], arr[0]  # 堆顶(最大)与最后一个交换
        for arr_len in range(self.length - 1, 1, -1):  # 从 self.length - 1 开始，逐步缩小堆的范围，直到堆中只剩 2 个元素。
            self.adjust_max_heap(0, arr_len)  # 调整堆，确保堆顶元素是当前堆中的最大值。
            arr[0], arr[arr_len - 1] = arr[arr_len - 1], arr[0]  # 将堆顶元素（当前最大值）与堆的最后一个元素交换。
            # 最后会交换一次，故for里面是到1


if __name__ == '__main__':
    my_sort = Sort(10)
    print('随机数', my_sort.arr)
    my_sort.QuickSort(0, my_sort.length - 1)
    print('排序后', my_sort.arr)
    print('共递归次数：', my_sort.count)
    my_sort2 = Sort(10)
    print('随机数', my_sort2.arr)
    my_sort2.Heap_Sort()
    print('排序后', my_sort2.arr)
